/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BASB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH25/FONT#8=FIX25



␈↓ α∧␈↓α11. Representation of LISP functions as lists.

␈↓ α∧␈↓␈↓ αTThe␈α
notation␈α
for␈α
LISP␈α∞functions␈α
used␈α
up␈α
to␈α
now␈α∞has␈α
been␈α
chosen␈α
for␈α
the␈α∞convenience␈α
of
␈↓ α∧␈↓the␈α⊃reader.␈α⊃ It␈α⊃is␈α⊃not␈α⊃the␈α⊃most␈α⊃convenient␈α⊃notation␈α⊃for␈α⊃writing␈α⊃with␈α⊃its␈α⊃finicky␈α⊂typographical
␈↓ α∧␈↓distinctions,␈α∞and␈α∂it␈α∞is␈α∞not␈α∂a␈α∞good␈α∂notation␈α∞for␈α∞writing␈α∂programs␈α∞that␈α∞are␈α∂to␈α∞be␈α∂manipulated␈α∞by
␈↓ α∧␈↓other␈α
programs.␈α
 For␈α
the␈αlatter␈α
purpose,␈α
it␈α
is␈α
convenient␈αto␈α
represent␈α
LISP␈α
functions␈αand␈α
programs
␈↓ α∧␈↓by␈α∞LISP␈α∞lists.␈α∞ In␈α∞fact,␈α∂however,␈α∞most␈α∞LISP␈α∞systems␈α∞use␈α∂the␈α∞list␈α∞notation␈α∞for␈α∞LISP␈α∂functions␈α∞as
␈↓ α∧␈↓their primary form of input.

␈↓ α∧␈↓␈↓ αTLISP␈α∪function␈α∀definitions␈α∪are␈α∪built␈α∀up␈α∪from␈α∪variables␈α∀and␈α∪constant␈α∀S-expressions␈α∪by
␈↓ α∧␈↓applying functions, by conditional expressions and by recursion.  Thus the function definition

␈↓ α∧␈↓␈↓ αT␈↓↓insa x ← ␈↓αif n␈↓↓ x ␈↓αthen␈↓ NIL ␈↓αelse␈↓ A . [␈↓αa␈↓↓ x . insa ␈↓αd␈↓↓ x]␈↓

␈↓ α∧␈↓has␈αthe␈α
variable␈α␈↓↓x␈↓␈αand␈α
the␈αatom␈αA␈α
at␈αthe␈αbase␈α
of␈αits␈αstructure␈α
and␈αapplies␈αto␈α
them␈αthe␈αbasic␈α
LISP
␈↓ α∧␈↓functions,␈α
the␈α∞function␈α
␈↓↓insa␈↓␈α∞being␈α
defined,␈α∞conditional␈α
expressions␈α∞and␈α
recursion.␈α∞ Therefore,␈α
in
␈↓ α∧␈↓order␈αto␈αwrite␈α
such␈αa␈αfunction␈α
as␈αa␈αLISP␈α
list,␈αwe␈αrequire␈α
notations␈αfor␈αall␈α
of␈αthese.␈α We␈αproceed␈α
as
␈↓ α∧␈↓follows:

␈↓ α∧␈↓␈↓ αT1. A variable is translated into the same letter capitalized so that ␈↓↓x␈↓ becomes X.

␈↓ α∧␈↓␈↓ αT2.␈α∂An␈α∞S-expression␈α∂such␈α∞as␈α∂the␈α∞atom␈α∂A␈α∞above␈α∂or␈α∞(CAR␈α∂X)␈α∞cannot␈α∂be␈α∞used␈α∂to␈α∞represent
␈↓ α∧␈↓itself,␈αbecause␈αany␈αS-expression␈αcan␈αoccur␈αincluding␈αthose␈αgiven␈αother␈αinterpretations.␈α Therefore,
␈↓ α∧␈↓an␈α
S-expression␈α
␈↓↓e␈↓␈αis␈α
translated␈α
into␈α
(QUOTE␈αe).␈α
 Thus␈α
A␈α
becomes␈α(QUOTE␈α
A)␈α
and␈α
(CAR␈αX)
␈↓ α∧␈↓becomes␈α⊃(QUOTE␈α⊃(CAR␈α⊃X)).␈α⊃ NIL␈α⊃and␈α⊃T␈α⊃occur␈α⊃so␈α⊃frequently␈α⊃that␈α⊃they␈α⊃are␈α⊃represented␈α⊂by
␈↓ α∧␈↓themselves␈α
instead␈α
of␈α
with␈α
QUOTE.␈α
 Thus␈α∞we␈α
write␈α
NIL␈α
for␈α
NIL␈α
instead␈α
of␈α∞writing␈α
(QUOTE
␈↓ α∧␈↓NIL)␈αas␈αour␈αtranslation␈αrule␈αwould␈αotherwise␈αrequire.␈α (This␈αconvention␈αdoes␈αnot␈αintroduce␈αa␈αreal
␈↓ α∧␈↓anomaly, because it amounts to considering NIL a variable whose value is NIL).

␈↓ α∧␈↓␈↓ αT3.␈αFunction␈α
names␈αare␈αrepresented␈α
by␈αatomic␈αsymbols␈α
so␈αthat␈α␈↓↓insa␈↓␈α
is␈αrepresented␈α
by␈αINSA.
␈↓ α∧␈↓The basic LISP functions are called CAR, CDR, CONS, ATOM and EQ.

␈↓ α∧␈↓␈↓ αT4.␈α⊂The␈α⊂application␈α∂of␈α⊂a␈α⊂function␈α⊂to␈α∂arguments␈α⊂is␈α⊂represented␈α⊂by␈α∂a␈α⊂list␈α⊂consisting␈α⊂of␈α∂the
␈↓ α∧␈↓function␈α⊂name␈α⊂followed␈α⊃by␈α⊂the␈α⊂arguments␈α⊃just␈α⊂as␈α⊂we␈α⊂have␈α⊃done␈α⊂with␈α⊂arithmetic␈α⊃functions␈α⊂in
␈↓ α∧␈↓previous␈α
examples.␈α
 Thus␈α␈↓↓insa␈α
x␈↓␈α
translates␈αto␈α
(INSA␈α
X),␈α␈↓αn␈α
␈↓↓x␈↓␈α
translates␈αto␈α
(NULL␈α
X),␈αand␈α
A␈α
.␈α[␈↓αa␈α
␈↓↓x
␈↓ α∧␈↓↓. insa ␈↓αd␈↓↓ x␈↓] translates to (CONS (QUOTE A) (CONS (CAR X) (INSA (CDR X)))).

␈↓ α∧␈↓␈↓ αT5. The conditional expression

␈↓ α∧␈↓␈↓αif␈↓↓ p1 ␈↓αthen␈↓↓ a1 ␈↓αelse if␈↓↓ p2 ␈↓αthen␈↓↓ a2 ␈↓αelse␈↓↓ ... ␈↓αelse␈↓↓ pn␈↓

␈↓ α∧␈↓is␈αrepresented␈α
by␈α(COND␈α
(p1␈αa1)␈α
(p2␈αa2)␈α
...␈α(T␈αan)),␈α
so␈αthat␈α
the␈αright␈α
side␈αof␈α
the␈αdefinition␈αof␈α
␈↓↓insa␈↓
␈↓ α∧␈↓becomes

␈↓ α∧␈↓(COND ((NULL X) NIL) (T (CONS (QUOTE A) (CONS (CAR X) (INSA (CDR X))))).

␈↓ α∧␈↓␈↓ αT6. λ␈↓↓x ... z.e␈↓ is represented by (LAMBDA (x ... z) e).


␈↓ α∧␈↓␈↓ ε|1␈↓ ∧



␈↓ α∧␈↓␈↓ αT7. ␈↓αlabel␈↓↓[f,e] is represented by (LABEL f e).

␈↓ α∧␈↓␈↓ αT8.␈α
The␈α
way␈αfunction␈α
definitions␈α
are␈α
represented␈αis,␈α
alas,␈α
implementation␈α
dependent.␈α Many
␈↓ α∧␈↓PDP-10 systems use

␈↓ α∧␈↓(DE <function name> <list of argument variables> <expression defining function>)

␈↓ α∧␈↓so that ␈↓↓insa␈↓ is finally defined by

␈↓ α∧␈↓(DE␈α⊂INSA␈α∂(X)␈α⊂(COND␈α∂((NULL␈α⊂X)␈α∂NIL)␈α⊂(T␈α∂(CONS␈α⊂(QUOTE␈α∂A)␈α⊂(CONS␈α∂(CAR␈α⊂X)␈α∂(INSA
␈↓ α∧␈↓(CDR X)))))).

␈↓ α∧␈↓␈↓ αTAs a second example, our old friend ␈↓↓alt␈↓ is given by

␈↓ α∧␈↓(DE␈α⊃ALT␈α⊃(X)␈α⊂(COND␈α⊃((OR␈α⊃(NULL␈α⊂X)␈α⊃(NULL␈α⊃(CDR␈α⊂X))␈α⊃X)␈α⊃(T␈α⊂(CONS␈α⊃(CAR␈α⊃X)␈α⊂(ALT
␈↓ α∧␈↓(CDDR X)))))).

␈↓ α∧␈↓␈↓ αTAs␈α∞you␈α∞see,␈α∞this␈α∞is␈α∞much␈α∂less␈α∞readable␈α∞than␈α∞the␈α∞publication␈α∞language␈α∞we␈α∂have␈α∞heretofore
␈↓ α∧␈↓used,␈αbut␈αit␈αis␈αmuch␈αmore␈αusable␈αby␈αa␈αLISP␈αprogram,␈αbecause␈αit␈αtakes␈αthe␈αform␈αof␈αLISP␈αdata.␈α In
␈↓ α∧␈↓this␈αbook,␈αwe␈αshall␈αcontinue␈αto␈αuse␈α
the␈αpublication␈αlanguage,␈αbut␈αthe␈αinternal␈αlanguage␈α
will␈αcome
␈↓ α∧␈↓up again when we discuss programs that interpret, translate, and create LISP programs.




























␈↓ α∧␈↓␈↓ ε|2␈↓ ∧